# -*- coding: utf-8 *-*
'''
@author: Geraldo Oliveira
@date: 13 de abril de 2013
@obs: 
Algoritmo de ordenacao MergeSort
'''

import math
import sys

'''
ordena uma lista utilizando o algoritmo mergesort
'''
class MergeSort(object):

	def __init__(self, lista):
		'''
		Recebe a lista a ordenar

			lista  -> Lista a ordenar
		'''
		self.lista = lista

	def run(self):
		'''
		Executa o metodo de ordenacao internamente
		'''
	 	self.sort()

	def sort(self, frm=0, to=None):
		'''	
		Algoritmo InsertionSort 
		'''
		if to is None: 
			to = len(self.lista)
		if to-frm <2 : 
			return
		middle = (frm + to) / 2
		self.sort(frm, middle)
		self.sort(middle, to)
		self.merge(frm, middle, to, middle-frm, to-middle)


	def merge(self, frm, pivot, to, len1, len2):
		'''	
		Funcao Merge do algoritmo InsertionSort

		Recebe:
			frm 	-> lista
			pivot 	-> posicao do pivot
			to 		-> posicao 
			len1 	-> tamanho lista 1
			len2 	-> tamanho lista 2
		'''
		if len1 == 0 or len2 == 0: 
			return
		if len1 + len2 == 2:
			if self.lista[pivot]<self.lista[frm]: 
				self.lista[pivot], self.lista[frm] = self.lista[frm], self.lista[pivot]
			return
		if len1 > len2:
			len11 = len1/2
			firstcut, secondcut, length = frm+len11, pivot, to-pivot
			while length > 0:
				half = length / 2
				mid = secondcut + half
				if self.lista[mid] < self.lista[firstcut]: 
					secondcut, length = mid+1, length-half-1
				else: 
					length = half
			len22 = secondcut - pivot
		else:
			len22 = len2/2
			firstcut, secondcut, length = frm, pivot+len22, pivot-frm
			while length > 0:
				half = length / 2
				mid = firstcut+half
				if self.lista[secondcut]<self.lista[mid]: 
					length = half
				else: 
					firstcut, length = mid + 1, length-half - 1
			len11 = firstcut-frm
		if firstcut != pivot and pivot != secondcut:
			n, m = secondcut-firstcut, pivot-firstcut
			while m != 0: n, m = m, n % m
			while n != 0:
				n -= 1
				p1, p2 = firstcut+n, n + pivot
				val, shift = self.lista[p1], p2 - p1
				while p2 != firstcut + n:
					self.lista[p1], p1 = self.lista[p2], p2
					if secondcut-p2 > shift: 
						p2 += shift
					else: 
						p2 = pivot-secondcut + p2
				self.lista[p1] = val
		newmid = firstcut + len22
		self.merge(frm, firstcut, newmid, len11, len22)
		self.merge(newmid, secondcut, to, len1 - len11, len2 - len22)

	def nome(self):
		'''
		Devolve o nome do metodo de ordenacao
		'''
		return "mergesort"

	def o(self, n):
		'''
		Calculo do valor teorico

		Recebe:
			n 	-> numero de elementos
		'''
		return (n * math.log(n))

	def __str__(self):
		'''
		Imprime o objecto 
		'''
		return str(self.lista)